package _interview100;

import _object.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 */
public class No124 {
    private int ans;

    public int maxPathSum(TreeNode root) {
        ans = root.val;
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftSum = Math.max(dfs(node.left), 0);
        int rightSum = Math.max(dfs(node.right), 0);
        ans = Math.max(leftSum + rightSum + node.val, ans);
        return Math.max(leftSum, rightSum) + node.val;
    }
}
